This invention relates to wireless sensor networks and, more particularly, to methods of wirelessly reprogramming sensor nodes securely and in an energy-efficient manner over multiple hops. Reprogramming becomes necessary when new functionality is desired, for example, or when it is required to modify existing functionality, e.g., by changing a parameter or parameters.
Large scale sensor networks may be deployed for long periods of time during which the requirements from the network or the environment in which the nodes are deployed may change. The change may necessitate uploading a new version of existing code or retasking the existing code with different sets of parameters. A primary requirement is that the reprogramming be done while the nodes are in situ, embedded in their sensing environment. This has spurred interest in remote multihop reprogramming protocols over the wireless link. For such reprogramming, it is desirable to have the code updates be 100% reliable and reach all desired destination nodes. This is a challenge since the network's functionality is likely degraded, if not reduced to zero, during the period when the nodes are being reprogrammed. Another challenge is to minimize the resource cost of the reprogramming and querying for availability of new code.
Several sensor network reprogramming approaches have appeared in the literature. TinyOS includes limited support for network programming via XNP (Crossbow Network Programming). However, XNP only operates over a single hop and does not provide incremental updates of a code image. The Multihop Over the Air Programming (MOAP) protocol extends this to operate over multiple hops. MOAP introduced several concepts which are used by later protocols, such as local recovery using unicast NACKs and broadcast of the code. However, MOAP does not leverage the pipelining effect with segments of the code image. Two more sophisticated protocols are Deluge and MNP, respectively described in the following papers which are hereby incorporated by reference: J. W. Hui and D. Culler, “The Dynamic Behavior of a Data Dissemination Protocol for Network Programming at Scale,” at the Proceedings of the 2nd international conference on Embedded networked sensor systems, Baltimore, Md., USA, pp. 81-94, 2004; S. S. Kulkarni and L. Wang. “MNP: Multihop Network Reprogramming Service for Sensor Networks,” at the 25th IEEE International Conference on Distributed Computing Systems, pp. 7-16, 2005.
Deluge and MNP both use a three-way handshake and segmentation into pages and packets. A binary image to be transmitted to the sensor nodes is initially only available from a few sources, e.g., base stations located in the sensor field. The code progressively ripples through the network with the exchange happening between neighbors through a three-way handshake of advertisement, request, and actual code transfer. The advertisement and the request may collectively be referred to as meta-data. The meta-data is typically much smaller in size than the code and is used to suppress redundant data transmission. Deluge builds on a protocol known as Trickle which determines when to propagate code in a one-hop case. Deluge leverages overheard advertisements or requests to decide when to create a new advertisement or send a new code update. MNP is designed in part to choose a local source of the code which can satisfy the maximum number of nodes. It provides energy savings by turning off the radio of all the nodes that are not selected as the sender. While this protocol does provide advantages, it has been found to download code significantly more slowly than Deluge.
While useful methods of reprogramming wireless multi-hop sensor networks are known, there remains a need for greater energy efficiency while preserving reliability of code dissemination in a multi-hop sensor network, as well as a need for improvements in overall performance in terms of the combination of reliability, efficiency and speed.
Security is another issue of concern for sensor networks, which are being deployed in situations where it is important to protect the message communication from eavesdropping or tampering. The deployments in military situations in hostile territory have strict security requirements for message communication. Some deployments in civilian situations have security requirements as well, e.g., in patient monitoring systems where communications should be secured for privacy reasons. A sensor network used for monitoring environmental conditions in public places (such as, concentration of toxins in the air, biometric sensors in airports) should have its inter-node communication protected against tampering as a guard against possible terrorist attacks directed to critical civilian infrastructures. These networks must also continue to function correctly in the event of certain nodes being taken over by an adversary.
Cryptography is the foundational technology used for protecting and securing the communication in sensor networks. This technology relies on keys as the centerpieces, and many attacks focus on disclosing these keys. This makes the management of the keys (the process by which keys are generated, stored, protected, distributed, used, and destroyed) in a large-scale network of up to hundreds of thousands of sensor nodes a very important and challenging problem. Sensor nodes are constrained in their energy availability, memory and computational resources, and communication bandwidth. These constraints make it impractical to use asymmetric algorithms for key management. These algorithms are very computationally intensive, and consequently, energy intensive since at their heart they involve exponentiation and modulus operations of large numbers. The common approach, therefore, is to use symmetric key cryptography where the two end-points of a communication share a secret key. The challenge is to manage the keys for symmetric cryptography in a scalable manner. The scalability goal implies that the end-to-end communication delay, energy overhead for key management, and the dollar cost of deployment should increase gradually with increasing size of the sensor network. Since the sensor nodes may be placed in hostile environments, we must also design for the possibility that some nodes may be taken over or compromised. The sensor nodes are inherently less reliable than wired platforms and therefore, a protocol must be designed to function in the face of some nodes being unavailable. Radio communication is recognized as more energy consuming than computation by several orders of magnitude. Consequently, the key management protocol should minimize the number of overhead control messages and the overhead number of bytes added to data messages.
Some symmetric key management protocols rely on a common shared secret key between all the nodes in the network leading to a highly insecure deployment. At the other end of the spectrum, some protocols have a separate shared key for each pair of nodes, which leads to a large amount of key storage that grows as the square of the number of nodes, and is therefore not scalable. The requirement to minimize communication overhead makes most of the proposed purely symmetric algorithms impractical since they add a fixed size overhead number of bytes to the payload and sensor networks typically have small sized packets.
Many key management protocols for ad-hoc networks have been proposed in the literaturem but they suffer from one or more of the problems of weak security guarantees if some nodes are compromised, lack of scalability, high energy overhead for key management, and increased end-to-end data latency.